// 判断二分图

package Leetcode;

import java.util.LinkedList;

// 使用并查集
class Solution785_1 {
    public boolean isBipartite(int[][] graph) {
        UnionFind uf = new UnionFind(graph.length);
        for (int i = 0; i < graph.length; i++) {
            int[] edge = graph[i];
            for (int vertex : edge) {
                if (uf.isSameUnion(vertex, i))
                    return false;
                // 将该点的邻接点加入同一个集合中
                uf.union(vertex, edge[0]);
            }
        }
        return true;
    }

    class UnionFind {
        int[] parent;

        public UnionFind(int length) {
            parent = new int[length];
            for (int i = 0; i < length; i++)
                parent[i] = i;
        }

        public int find(int idx) {
            return parent[idx] == idx ? parent[idx] : find(parent[idx]);
        }

        public void union(int a, int b) {
            if (isSameUnion(a, b) == false)
                parent[a] = find(b);
        }

        // 判断两个值是否为同一集合
        public boolean isSameUnion(int a, int b) {
            return find(a) == find(b);
        }
    }
}

// 广度优先遍历
class Solution785_2 {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length]; // 1和-1，初始为0
        LinkedList<Integer> queue = new LinkedList<>();

        for (int i = 0; i < graph.length; i++) {
            // 如果该点已经被遍历过，即赋值为1，-1
            if (color[i] != 0)
                continue;

            color[i] = 1;
            queue.addLast(i);
            while (!queue.isEmpty()) {
                int first = queue.pollFirst();
                for (int vertex : graph[first]) {
                    // 如果邻接点染色值相同
                    if (color[first] == color[vertex])
                        return false;
                    // 如果邻接点并没有被染色
                    else if (color[vertex] == 0) {
                        color[vertex] = -color[first];
                        queue.addLast(vertex);
                    }
                } // for-vertex
            } // while-queue
        } // for-i
        return true;
    }
}

// 深度优先遍历
class Solution785_3 {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            // 如果以初始点开始深度染色发现返回值为false
            if (color[i] == 0 && !dfs(graph, i, 1, color))
                return false;
        }
        return true;
    }

    // 对顶点index染色color，并深度递归，如果无法染色返回false，否则返回true
    public boolean dfs(int[][] graph, int index, int value, int[] color) {
        // 如果要对顶点染色时发现已经被染色了，判断染色是否相同
        if (color[index] != 0)
            return color[index] == value;

        // 染色并让邻接点染逆色
        color[index] = value;
        for (int vertex : graph[index]) {
            if (!dfs(graph, vertex, -color[index], color))
                return false;
        }
        return true;
    }
}